# -*- coding: utf-8 -*-
# @File      :3
# @Author    :liaogan
# @Datetime  :2023/3/21 19:46


"""
dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1])

其中dp[i-1][j]表示从上面的格子到达当前格子的最小路径和，dp[i][j-1]表示从左边的格子到达当前格子的最小路径和。我们取两者中的较小值再加上当前格子的数字，就是到达当前格子的最小路径和。

最终dp[m-1][n-1]即为从左上角到右下角的最小路径和。

"""
def minPathSum(grid):
    m, n = len(grid), len(grid[0])
    dp = [[0] * n for _ in range(m)]
    dp[0][0] = grid[0][0]
    # 初始化第一行和第一列
    for i in range(1, m):
        dp[i][0] = dp[i-1][0] + grid[i][0]
    for j in range(1, n):
        dp[0][j] = dp[0][j-1] + grid[0][j]
    # 状态转移
    for i in range(1, m):
        for j in range(1, n):
            dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1])
    return dp[m-1][n-1]


minPathSum(grid=[1][2][3])